package bTree.LeetCode;

public class 排列序列 {
    String res = "";
    int cnt = 0;
    int cont=1;

    public String getPermutation(int n, int k) {
        boolean[] visited = new boolean[n];
        StringBuilder sb = new StringBuilder();
        backTracking(n, k, visited, sb);
        return res;
    }

    private void backTracking(int n, int k, boolean[] visited, StringBuilder sb) {

        if (sb.length() == n) {
            cnt++;
            if (cnt == k) {
                res = sb.toString();
                cont=0;
            }
            return;
        }
        for (int i = 1; i <= n; i++) {
            if(cont==0){
                return;
            }
            if (!visited[i-1]) {
                sb.append(i);
                visited[i-1] = true;
                backTracking(n, k, visited, sb);
                sb.deleteCharAt(sb.length() - 1);
                visited[i-1] = false;
            }
        }
    }
}